import java.util.Arrays;

public class ShellSort {
    public static void shellsort(int[] arr){
        int gap= arr.length/2;
        while(gap>=1){
            shell(arr,gap);
            gap/=2;
        }
    }

    private static void shell(int[] arr, int gap) {
        for (int i = gap; i<arr.length ; i++) {
            int index=i-gap,indexVal=arr[i];
            for (; index >=0 ; index-=gap) {
                if(arr[index]>indexVal){
                    arr[index+gap]=arr[index];
                }else{
                    break;
                }
            }arr[index+gap]=indexVal;


        }
    }
    public static void main(String[] args) {
        int[] arr={8,4894,8468,4684,684,68468,4846,4,864,64,64,6,484,6,46,48,4,81,1,2,8,5,484,84,8,48,4};
        shellsort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
